package com.zklh.leetcode.constructor.uf;

/**
 * 并查集实现
 *
 * @author 坐看落花
 * @version 1.0
 * @date 2021/6/5 15:28
 */
public class UFImpl implements UF {

    /**
     * 索引表示节点, 值表示节点相连的父节点, 默认情况下只和自己相连
     */
    private int[] parent;
    private int[] size;
    private int count;


    public UFImpl( int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
        count = n;
    }

    @Override
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);

        if (rootP == rootQ) {
            return;
        }
        if (size[rootP] > size[rootQ]) {
            parent[rootQ] = rootP;
            size[rootP] +=1;
        } else {
            parent[rootP] = rootQ;
            size[rootQ] +=1;
        }
        count--;
    }


    /**
     * 寻找当前节点相连的最顶层父节点
     * @param x
     * @return
     */
    private int find(int x) {
        while (x != parent[x]) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    @Override
    public boolean connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }

    @Override
    public int count() {
        return count;
    }

    public static void main(String[] args) {
        UF uf = new UFImpl(10);

        uf.union(1,2);
        uf.union(2,3);
        uf.union(6,7);
        uf.union(5,7);
        uf.union(8,9);

        boolean connected = uf.connected(3, 7);
        boolean connected1 = uf.connected(1, 3);
        int count = uf.count();
    }
}
